class Solution
{
public:
    vector<int> postorderTraversal(TreeNode *root)
    {
        stack<TreeNode *> stk;
        vector<int> res;

        if (root == NULL)
            return res;

        stk.push(root);
        while (!stk.empty())
        {
            TreeNode *node = stk.top();

            if (node->left == NULL && node->right == NULL)
            {
                res.push_back(node->val);
                stk.pop();
            }
            else
            {
                if (node->right)
                {
                    stk.push(node->right);
                    node->right = NULL;
                }
                
                if (node->left)
                {
                    stk.push(node->left);
                    node->left = NULL;
                }
            }
        }
        return res;
    }
};